package 力扣.动态规划;

import java.util.Arrays;

//给定一个字符串 S，计算 S 的不同非空子序列的个数。
//因为结果可能很大，所以返回答案模 10^9 + 7.
public class 不同子序列2 {
    public static void main(String[] args) {
        int abc = distinctSubseqII("aba");
        System.out.println(abc);
    }
    public static int distinctSubseqII(String S) {
        int m = 1000000000+7;
        int len=S.length();
        int[] dp = new int[len + 1];
        dp[0]=1;
        int[] ints = new int[26];
        Arrays.fill(ints,-1);
        for (int i = 0; i <len; i++) {
            int x=S.charAt(i)-'a';
            dp[i+1]=2*dp[i]%m;
            if (ints[x]!=-1)
                dp[i+1]-=dp[ints[x]];
            dp[i+1]%=m;
            ints[x]=i;
        }
        //减去空字符串
        dp[len]--;
        return dp[len]<0?dp[len]+m:dp[len];
    }
}
